这道题用后缀自动机可以暴力解决。
建好后缀自动机后 , 因为起点到后缀自动机上的每一个点都是一个本质不同的子串 , 我们就可以在 上 。 表示包含转移的子串数量,很容易列出转移式:
注意虽然是一个,但是我们并不需要把图建出,只需要用拓扑序就可以了。
注意,此题不一定是小写字母!!!
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 1000 , MAXK = 256;
struct Suffix_Automaton {
int Root , Size , Last , Maxlen[ 2 * MAXN + 5 ];
int Trans[ 2 * MAXN + 5 ][ MAXK + 5 ] , Link[ 2 * MAXN + 5 ];
long long dp[ 2 * MAXN + 5 ];
Suffix_Automaton( ) { Root = Size = Last = 1; }
void Copy( int u , int v ) {
for( int i = 1 ; i <= MAXK ; i ++ )
Trans[ u ][ i ] = Trans[ v ][ i ];
}
void Extend( int chr ) {
int Newnode = ++ Size , u = Last;
Maxlen[ Newnode ] = Maxlen[ u ] + 1;
for( ; u && !Trans[ u ][ chr ] ; u = Link[ u ] )
Trans[ u ][ chr ] = Newnode;
if( !u ) Link[ Newnode ] = 1;
else {
int v = Trans[ u ][ chr ];
if( Maxlen[ v ] == Maxlen[ u ] + 1 ) Link[ Newnode ] = v;
else {
int w = ++ Size;
Copy( w , v ); Maxlen[ w ] = Maxlen[ u ] + 1;
for( ; u && Trans[ u ][ chr ] == v ; u = Link[ u ] ) Trans[ u ][ chr ] = w;
Link[ w ] = Link[ v ];
Link[ v ] = Link[ Newnode ] = w;
}
}
Last = Newnode;
}
void Build( char *str ) {
Root = Size = Last = 1;
memset( Trans , 0 , sizeof( Trans ) );
memset( Link , 0 , sizeof( Link ) );
memset( dp , 0 , sizeof( dp ) );
memset( tot , 0 , sizeof( tot ) );
int len = strlen( str );
for( int i = 0 ; i < len ; i ++ )
Extend( str[ i ] );
Sort( );
}
int tot[ 2 * MAXN + 5 ] , Topu[ 2 * MAXN + 5 ];
void Sort( ) {
for( int i = 1 ; i <= Size ; i ++ ) tot[ Maxlen[ i ] ] ++;
for( int i = 1 ; i <= Size ; i ++ ) tot[ i ] += tot[ i - 1 ];
for( int i = 1 ; i <= Size ; i ++ ) Topu[ tot[ Maxlen[ i ] ] -- ] = i;
}
long long Dp( ) {
for( int i = Size ; i >= 1 ; i -- ) { //深度从大到小
int u = Topu[ i ];
dp[ u ] = ( u > 1 );
for( int k = 1 ; k <= MAXK ; k ++ )
if( Trans[ u ][ k ] ) dp[ u ] += dp[ Trans[ u ][ k ] ];
}
return dp[ Topu[ Root ] ]; //这里写成dp[ Root ]也没有问题,起点的拓扑序一定是最大的
}
}SAM;
int t;
char str[ MAXN + 5 ];
int main( ) {
scanf("%d",&t);
while( t -- ) {
scanf("%s", str );
SAM.Build( str );
printf("%lld\n", SAM.Dp( ) );
}
return 0;
}